## 双指针法解数组题：
# 一、快慢指针：原地修改数组的题目
# 1. 26 原地删除有序数组里的重复元素（只保留一个），要求返回的是原数组中唯一元素的个数：
# 思路：看下面代码，因为这个题目要求返回的是唯一元素的个数，遍历中其实是使用了slow指针来达到目的
# 我觉得有点难！！ ⭐
class Delete_Dup_list(object):
    def solution(self,nums):
        # 边遍历边改，一个慢指针，一个快指针：
        fast, slow = 0,0
        while fast<len(nums):
            if nums[slow] != nums[fast]:
                slow+=1
                nums[slow]=nums[fast]
            # 移动快指针
            fast+=1
        return slow+1 # nums
    def test(self):
        nums=[1,2,2,2,3,5,6,6,7]
        res = self.solution(nums)
        print('结果是：',res)
# 2. 27 原地移除数组nums中值为val的元素，原始的元素顺序可以发生改变
# 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
#
# - 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。（这里后半段话是重点）
# - 返回 k。
# 思路：和上面的题目思路是一样的，不同的是fast指针遇到val值跳过即可得到我们想要的结果，挺巧妙的，慢慢学！！★

class Delete_Certain_Elements(object):
    def solution(self,nums,val):
        slow=0
        fast=0
        while fast<len(nums):
            if nums[fast]!=val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow
    def test(self):
        nums=[1,2,2,5,6,2,3,0]
        val = 2
        res = self.solution(nums,val)
        print(res)

# 类似的我们可以解决另外一个题目：283 原地修改，将数组中的所有值为 0 的元素移到数组末尾
# 在上一题目的基础上，得到k之后，把后面的值都赋值为0就完事了
class Move_Zeros(object):
    def solution(self,nums):
        slow,fast=0,0
        while fast<len(nums):
            if nums[fast]!=0:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        for i in range(slow,len(nums)):
            nums[i]=0
        return nums
    def test(self):
        nums=[2,1,0,2,5,0,6,0,8,0]
        res=self.solution(nums)
        print(res)

# 二、滑动窗口法：
# left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题
# 滑动窗口的标准化伪代码：
'''
def window(nums):
    left=0
    right=0
    while right<len(nums):
        # 增大窗口：
        window.addLast(nums[right])
        right+=1
        while(windos needs shrink):
            window.removeFirst(nums[left])
            left-=1
'''
# 三、经典左右指针解决算法问题：
# 1. 二分查找：
# 先只了解简单问题： 一个有序数组nums，给你target，如果存在target请返回给我索引，否则返回-1：
# 有一些复杂的变体暂时先不管
class Dichotomy(object):
    def solution(self,nums,target):
        # 明确左右指针的取法和边界条件：
        left=0
        right=len(nums)-1
        mid=(right+left)//2
        while left<=right:
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
            else:
                return mid
            mid = (right + left) // 2
        return -1
    def test(self):
        nums=[1,2,3,6,6,8,9,10,11]
        target=10
        res = self.solution(nums,target)
        print(res)
# 2.167. 两数之和 II
# 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
#
# 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
#
# 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
#
# 你所设计的解决方案必须只使用常量级的额外空间。
# 思路：有序数组就可以想到类二分法：!!! ★★
class Find_Ordered_Sum(object):
    def solution(self,nums,target):
        left=0
        right=len(nums)-1
        while left<right:
            sum=nums[left]+nums[right]
            if sum<target:
                # 小移动左指针：
                left+=1
            elif sum>target:
                right-=1
            else:
                return left+1,right+1
        return -1
    def test(self):
        nums=[2,7,11,15]
        target=9
        res = self.solution(nums,target)
        print(res)
# 3. 344 反转数组：
#编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
#不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
# 所谓的反转就是，索引为i的值和索引为len(s)-1-i的值交换, 字符串不允许索引赋值操作
class Reverse_String(object):
    def solution(self,s):
        # 有了规律连双指针都不需要
        lenth=len(s)-1
        for i in range(len(s)//2):
            left=s[i]
            right=s[lenth-i]
            s[i]=right
            s[lenth-i]=left
        return s
    def test(self):
        s=['1','2','s','e','s','f','5','p']
        res = self.solution(s)
        print(res)
# 4. 找到最长的回文串：
# 回文串指正着读和反着读是一样的的字符串
# 判断不难，找怎么找呢？
class Judge_Palindrome(object):
    def solution(self,nums):
        # 判断是否是是回文串：
        lenth=len(nums)-1
        for i in range(len(nums)//2):
            if nums[i]!=nums[lenth-i]:
                return 0
        return 1
    def test(self):
        nums=[1,1,2,2,1,1]
        res = self.solution(nums)
        print('是否是回文串：',res)

class Find_LongestPalindrome(object):
    def center_palindrome(self,l:int,r:int,nums)->list:
        # 从某个/2个中心点向两侧扩散，找到最长的回文串：
        while l>=0 and r<len(nums) and nums[l]==nums[r]:
            l-=1
            r+=1
        return nums[l+1:r] # 注意边界条件，因为最新的没有进入while条件，要回退一步
    def solution(self,nums):
        # 从中心向两侧出发的指针，要区分奇数偶数长度列表不同的情况；
        res=''
        for i in range(len(nums)):
            res1=self.center_palindrome(i,i,nums) # 奇数长度的
            res2=self.center_palindrome(i,i+1,nums) # 偶数长度的
            res=res1 if len(res1)>len(res) else res
            res=res2 if len(res2)>len(res) else res
        return res
    def test(self):
        nums='123321111222111'
        print(self.solution(nums))

if __name__=='__main__':
    Delete_Dup_list().test()